package sort;

/**
 * 快速排序3.0版本，时间复杂度O（N*logN），空间复杂度是O（logN）
 */
public class QuickSort {
    //快速排序
    public static void quicksort(int[]arrs,int l,int r){
        if (l<r){
            //随机交换数组最后一位，没有这个就是2.0版本
            swap(arrs,l+(int)(Math.random()*(r-l+1)),r);
            //获取中间数组的左右边界
            int[]p = partition(arrs,l,r);
            //递归快排左边界
            quicksort(arrs,l,p[0]-1);
            //递归快排右边界
            quicksort(arrs,p[1]+1,r);
        }
    }

    //排序
    private static int[] partition(int[] arrs, int l, int r) {
        int less = l-1;  //<区左边界
        int more = r;   //>区右边界
        while (l<more){  //l表示当前数的位置 arr[r]就是划分值
            if (arrs[l] < arrs[r]){ //当前数 < 划分值
                swap(arrs,++less,l++);
            }else if (arrs[l] > arrs[r]){ //当前数大于划分值
                swap(arrs,--more,l);
            }else{
                l++;
            }
        }
        swap(arrs,more,r);
        return new int[]{less+1,more};
    }

    //交换
    private static void swap(int[] arrs, int i, int r) {
        int temp = arrs[i];
        arrs[i] = arrs[r];
        arrs[r] = temp;
    }

    public static void main(String[] args) {
        int[] arrs = {1,4,7,9,2,34,6};
        quicksort(arrs,0,arrs.length-1);
        for (int arr : arrs) {
            System.out.println(arr);

        }
    }
}
